package com.lry.basic.algorithm.common;

/**
 * 最长公共子序列
 */
public class LongestCommonSubString {
    public static int longestCommonSubString(int[] A,int[] B){
        int[][] dp = new int[A.length+1][B.length+1];
        for(int i=0;i<A.length;i++){
            for(int j=0;j<B.length;j++){
                if(A[i]==B[j]){
                    dp[i+1][j+1] = dp[i][j]+1;
                }else{
                    dp[i+1][j+1] = Math.max(dp[i][j+1],dp[i+1][j]);
                }
            }
        }
        return dp[A.length][B.length];
    }

    public static void main(String[] args) {
        System.out.println(longestCommonSubString(new int[]{1,9,5,2,1,2},new int[]{1,3,7,1,2,5}));
    }
}
